package com.dmall.list;

/**
 * 使用递归算法实现的链表
 * @author xiao1.wang@dmall.com
 * @date 2019-07-16 23:30:17
 * @param <E> 泛型
 */
public class RecursiveLinkedList<E> {

    private class Node {

        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyHead;
    private int size;

    public RecursiveLinkedList() {
        this.dummyHead = new Node(null, null);
        this.size = 0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        add(index, e, this.dummyHead);
        size ++;
    }

    public void add(int index, E e, Node prev) {
        if(index <= 0){
            Node node = new Node(e);
            node.next = prev.next;
            prev.next = node;
            return;
        }
        add(index - 1, e, prev.next);
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    public E get(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        E result = get(index, dummyHead.next);
        return result;
    }

    private E get(int index, Node cur) {
        if (index <= 0) {
            return cur.e;
        }
        return get(index - 1, cur.next);
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size - 1);
    }

    public E set(int index, E newData) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal.");
        }

        E result = set(index, newData, dummyHead.next);
        return result;
    }

    private E set(int index, E newData, Node cur) {
        E e;
        if (index <= 0) {
            e = cur.e;
            cur.e = newData;
            return e;
        }
        return set(index - 1, newData, cur.next);
    }

    public boolean contains(E e) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.e.equals(e)) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("Index is illegal.");
        }
        E result = remove(index, dummyHead);
        size --;
        return result;
    }

    private E remove(int index, Node prev) {
        E e;
        if (index <= 0) {
            Node delNode = prev.next;
            e = delNode.e;
            prev.next = delNode.next;
            delNode.next = null;
            return e;
        }
        return remove(index - 1, prev.next);
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    public void reverse() {
        if (dummyHead.next == null || dummyHead.next.next == null) {
            return;
        }
        Node tempHead = new Node();
        Node curNode = dummyHead.next;
        while (curNode != null) {
            Node nextNode = curNode.next;
            curNode.next = tempHead.next;
            tempHead.next = curNode;
            curNode = nextNode;
        }
        dummyHead.next = tempHead.next;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = dummyHead.next;
        while (cur != null) {
            res.append(cur.e).append("->");
            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }
}
